package Aula21;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class BTreeImpl implements BTree {

	@Override
	public int procurar(BTreeNode raiz, int t, int chave) {
		if (isBTree(raiz, t)) {
			return buscaBTree(raiz, chave);
		}
		return -1;
	}

	private boolean isBTree(BTreeNode raiz, int t) {
		Stack<BTreeNode> pilha = new Stack<BTreeNode>();
		pilha.push(raiz);
		BTreeNode nodeBTree;
		KeyListNode nodeKeys;
		ChildrenListNode nodeSon;
		while (!pilha.isEmpty()) {
			nodeBTree = pilha.pop();
			nodeKeys = nodeBTree.keys;
			int i = 0;
			ArrayList<Integer> keys = new ArrayList<Integer>();
			ArrayList<Integer> keysCopy = new ArrayList<Integer>();

			while (nodeKeys != null) {
				i++;
				if (nodeKeys.key <= 0 || keys.contains(nodeKeys.key))
					return false;
				keys.add(nodeKeys.key);
				keysCopy.add(nodeKeys.key);
				nodeKeys = nodeKeys.next;
			}
			if (nodeBTree != raiz && (i > (t * 2) - 1 || i < t - 1)) {
				return false;
			}
			Collections.sort(keysCopy);
			if (!keys.equals(keysCopy)) {
				return false;
			}
			if (!nodeBTree.leaf) {
				nodeSon = nodeBTree.childrens;
				i = 0;
				while (nodeSon != null && nodeSon.child != null) {
					i++;
					pilha.push(nodeSon.child);
					nodeSon = nodeSon.next;
				}

				if (nodeBTree != raiz && (i > t * 2 || i < t)) {
					return false;
				}
			}
		}
		return true;
	}

	private int buscaBTree(BTreeNode raiz, int chave) {
		int i = 0;
		KeyListNode keyNode = raiz.keys;
		while (keyNode != null && chave > keyNode.key) {
			keyNode = keyNode.next;
			i++;
		}
		if (keyNode != null && chave == keyNode.key) {
			return chave;
		}
		if (raiz.leaf) {
			return 0;
		}
		BTreeNode filho = raiz.childrens.get(i);
		if (filho == null) {
			return 0;
		}
		return buscaBTree(filho, chave);
	}

	private void caso1(BTreeNode no, int chave) {
		no.keys.remove(chave);
		no.n--;
	}

	private void caso2a(BTreeNode no, int chave) {
		int i = no.keys.indexOf(chave);
		int antecessor = no.childrens.get(i).keys.last();
		no.childrens.get(i).keys.remove(antecessor);
		no.childrens.get(i).n--;
		no.keys.add(antecessor);
		no.keys.remove(chave);
	}

	private void caso2b(BTreeNode no, int chave) {
		int i = no.keys.indexOf(chave);
		int sucessor = no.childrens.get(i + 1).keys.get(0);
		no.childrens.get(i + 1).keys.remove(sucessor);
		no.childrens.get(i + 1).n--;
		no.keys.add(sucessor);
		no.keys.remove(chave);
	}

	private void caso2c(BTreeNode no, BTreeNode pai, int chave) {
		int i = no.keys.indexOf(chave);
		BTreeNode sucessor = no.childrens.get(i + 1);
		BTreeNode antecessor = no.childrens.get(i);
		ArrayList<BTreeNode> lista = new ArrayList<BTreeNode>();
		if (pai != null) {
			lista.add(antecessor);
			lista.add(sucessor);
			juntar(lista, antecessor);
			no.keys.remove(chave);
			no.n--;
			no.childrens.remove(sucessor);
		} else {
			lista.add(antecessor);
			lista.add(no);
			lista.add(sucessor);
			juntar(lista, no);
			no.childrens.remove(antecessor);
			no.childrens.remove(sucessor);
			no.keys.remove(chave);
			no.n--;
		}
		no.leaf = true;
		if(no.childrens != null)
			no.leaf = false;
	}

	private void juntar(ArrayList<BTreeNode> nodes, BTreeNode nodeJuntar) {
		BTreeNode node;
		KeyListNode keyNode;
		ChildrenListNode filhosNode;
		for (int i = 0; i < nodes.size(); i++) {
			node = nodes.get(i);
			if(node != nodeJuntar){
				keyNode = node.keys;
				for (; keyNode != null; nodeJuntar.n++) {
					nodeJuntar.keys.add(keyNode.key);
					keyNode = keyNode.next;
				}
				filhosNode = node.childrens;
				if (filhosNode != null) {
					if(nodeJuntar.childrens != null){
						while (filhosNode != null) {
							nodeJuntar.childrens.add(filhosNode);
							filhosNode = filhosNode.next;
						}
					}else{
						nodeJuntar.childrens = filhosNode.copy();
					}
				}
			}
		}
		nodeJuntar.leaf = true;
		if(nodeJuntar.childrens != null)
			nodeJuntar.leaf = false;
	}

	private void moverEsqDir(BTreeNode node, BTreeNode filhoEsq,
			BTreeNode filhoDir) {
		int chaveFilhoEsq = filhoEsq.keys.last();
		int chaveNode = node.keys.last();
		if (filhoEsq.childrens != null) {
			BTreeNode filho = filhoEsq.childrens.lastChild();
			ChildrenListNode newFilhosDir = new ChildrenListNode(filho,
					filhoDir.childrens);
			filhoEsq.childrens.remove(filho);
			filhoDir.childrens = newFilhosDir;
		}
		node.keys.add(chaveFilhoEsq);
		node.keys.remove(chaveNode);
		filhoDir.keys.add(chaveNode);
		filhoDir.n++;
		filhoEsq.keys.remove(chaveFilhoEsq);
		filhoEsq.n--;
	}

	private void moverDirEsq(BTreeNode node, BTreeNode filhoEsq,
			BTreeNode filhoDir) {
		int chaveFilhoDir = filhoDir.keys.get(0);
		int chaveNode = node.keys.get(0);
		if (filhoDir.childrens != null) {
			BTreeNode filho = filhoDir.childrens.get(0);
			filhoDir.childrens.remove(filho);
			filhoEsq.childrens.add(filho);
		}
		filhoDir.keys.remove(chaveFilhoDir);
		filhoDir.n--;
		node.keys.add(chaveFilhoDir);
		node.keys.remove(chaveNode);
		filhoEsq.keys.add(chaveNode);
		filhoEsq.n++;

	}

	private int remocaoBtree(BTreeNode nodeTree, BTreeNode pai, int t, int chave) {
		int i = 0;
		KeyListNode keyNode = nodeTree.keys;
		while (keyNode != null && chave > keyNode.key) {
			keyNode = keyNode.next;
			i++;
		}

		ChildrenListNode filhoEsqNode = nodeTree.childrens;
		ChildrenListNode filhoDirNode = nodeTree.childrens;
		for (; i > 0 && filhoEsqNode != null; i--) {
			filhoEsqNode = filhoEsqNode.next;
		}
		if (filhoEsqNode == null) {
			filhoDirNode = null;
		} else {
			filhoDirNode = filhoEsqNode.next;
		}

		if (keyNode != null && keyNode.key == chave) {

			if (nodeTree.leaf) {
				// caso1
				System.out.println("Caso 1");
				caso1(nodeTree, chave);
			} else {
				// caso 2

				if (filhoEsqNode != null && filhoEsqNode.child.n >= t) {
					// caso a
					System.out.println("Caso 2a");
					caso2a(nodeTree, chave);
				} else if (filhoDirNode != null && filhoDirNode.child.n >= t) {
					// caso b
					System.out.println("Caso 2b");
					caso2b(nodeTree, chave);
				} else {
					// caso c
					System.out.println("Caso 2c");
					caso2c(nodeTree, pai, chave);
				}
			}
			return chave;
		} else {
			// caso 3
			if (filhoEsqNode != null) {
				if (filhoEsqNode.child.n == t - 1) {
					ChildrenListNode filhoT = nodeTree.childrens;
					boolean filhoTChaves = false;
					while (filhoT != null) {
						if (filhoT.child.n >= t) {
							filhoTChaves = true;
							break;
						}
						filhoT = filhoT.next;
					}
					if (filhoTChaves) {
						// caso a
						i = nodeTree.childrens.indexOf(filhoEsqNode.child);
						int iIrmaoT = nodeTree.childrens.indexOf(filhoT.child);
						if (i > iIrmaoT) {
							moverEsqDir(nodeTree, filhoT.child, filhoEsqNode.child);
						} else {
							moverDirEsq(nodeTree, filhoEsqNode.child,
									filhoT.child);
						}
						System.out.println("Caso 3a");
					} else {
						// caso b
						ArrayList<BTreeNode> lista = new ArrayList<BTreeNode>();
						BTreeNode noAntecessor, noSucessor;
						if(filhoDirNode == null){
							noAntecessor = nodeTree.childrens.get(i - 1);
							noSucessor = filhoEsqNode.child;
						}else{
							noAntecessor = filhoEsqNode.child;
							noSucessor = filhoDirNode.child;
						}
						lista.add(noAntecessor);
						lista.add(nodeTree);
						lista.add(noSucessor);
						juntar(lista, nodeTree);
						nodeTree.childrens.remove(noSucessor);
						if(nodeTree.childrens.next == null)
							nodeTree.childrens = null;
						else
							nodeTree.childrens.remove(noAntecessor);
						System.out.println("Caso 3b");
						return remocaoBtree(nodeTree, pai, t, chave);
					}
				} else {
					// caso c esse else pode ser retirado!
					System.out.println("Caso 3c");
				}
				return remocaoBtree(filhoEsqNode.child, nodeTree, t, chave);
			}
		}
		return 0;
	}

	@Override
	public int remover(BTreeNode raiz, int t, int chave) {
		if (isBTree(raiz, t)) {
			return remocaoBtree(raiz, null, t, chave);
		}
		return -1;
	}

	public static void main(String[] args) {
		int t = 2;
		BTreeNode raiz = new BTreeNode(1, new KeyListNode(12), false);
		BTreeNode node11 = new BTreeNode(1, new KeyListNode(5), false);
		BTreeNode node12 = new BTreeNode(1, new KeyListNode(18), false);
		BTreeNode node21 = new BTreeNode(2, new KeyListNode(3, new KeyListNode(4)));
		BTreeNode node22 = new BTreeNode(2, new KeyListNode(6, new KeyListNode(8)));
		BTreeNode node23 = new BTreeNode(1, new KeyListNode(11));
		BTreeNode node24 = new BTreeNode(1, new KeyListNode(13));
		BTreeNode node25 = new BTreeNode(2, new KeyListNode(20, new KeyListNode(21)));
		BTreeNode node26 = new BTreeNode(1, new KeyListNode(40));
		raiz.childrens = new ChildrenListNode(node11, new ChildrenListNode(node12));
		node11.childrens = new ChildrenListNode(node21, new ChildrenListNode(node22));
		node12.childrens = new ChildrenListNode(node24, new ChildrenListNode(node25));
		BTree bTree = new BTreeImpl();
		System.out.println(bTree.remover(raiz, t, 21));
		System.out.println(bTree.remover(raiz, t, 21));
		System.out.println(bTree.remover(raiz, t, 12));
		System.out.println(bTree.remover(raiz, t, 18));
		System.out.println(bTree.remover(raiz, t, 4));
		System.out.println(bTree.remover(raiz, t, 13));
		System.out.println(bTree.remover(raiz, t, 13));
		System.out.println(bTree.remover(raiz, t, 8));
		System.out.println(bTree.remover(raiz, t, 20));
		System.out.println(bTree.remover(raiz, t, 6));
		System.out.println(raiz.keys);
		System.out.println(raiz.childrens.child.keys);
		System.out.println(bTree.remover(raiz, t, 5));
		System.out.println(bTree.remover(raiz, t, 13));
		System.out.println(raiz.keys);
	}

}
